﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using ShapeConnectors.MaTrix;
namespace ShapeConnectors
{
    class Dijkstra : MaTran
    {
        public static List<BuocThucHien > stepDisjtra=new List<BuocThucHien> ();
        public static List<CANHNA> cDisjtra = new List<CANHNA>();
        private int VOCUC = 10000;
        List<int> T = new List<int>();
        private int nT;
        List<int> D = new List<int>();
        List<int> LabelDijk = new List<int>();
        string chuoi = null;
        private int s;
        private int t;
        public void Nhap(int bd, int kt)
        {
                s = bd;
                t = kt;
        }
        public string XuatDijkstra()
        {
            int temp = D[t];
            int k = t;
            chuoi += "Đường đi từ " + t.ToString() + "đến " + s.ToString() + "là:";
            //if (LabelDijk[s] == -1)
            //    return "khong co duong di";
            while (k != s)
            {
                
                chuoi += k.ToString() + "->";
                k = LabelDijk[k];
            }
            chuoi+= s.ToString();
            chuoi += "\r\n Trọng lượng: "+temp.ToString();
            return chuoi;
        }
        public void KhoiTao()
        {
            nT = spt;
            for (int i = 0; i < spt; i++)
            {
               
                T.Add(1);
                D.Add(VOCUC);
                LabelDijk.Add(-1);
            }
            D[s] = 0;
        }
        public void DijkstraAlg(int j)
        {
            KhoiTao();
            int v = s;
            int min;
            while (T[t] == 1)
            {
                //BuocThucHien buocdisjtra=new BuocThucHien ();
                //buocdisjtra.KhoiTao();
                min = VOCUC;
                v = -1;
                for (int i = 0; i < nT; i++)
                {
                    if (T[i] != 0 && min >D[i])
                    {
                        min = D[i];
                        v = i;
                    }            
                    
                }
                if (v == -1)
                    return;
                T[v] = 0;
                //buocdisjtra.Dinhcanto = v;
                for (int k = 0; k < nT; k++)
                {
                    if (a[v, k] != 0 && D[k] > D[v] + a[v, k])
                    {
                        //CANHNA temp = new CANHNA();
                        //temp.SetDinh1(v);
                        //temp.SetDinh2(k);
                        //temp.SetTS(a[v,k]);
                        //buocdisjtra.Canhlienquan.Add(temp);
                        D[k] = D[v] = a[v, k];
                        LabelDijk[k] = v;
                        
                    }
                  
                }
                //stepDisjtra.Add(buocdisjtra);
            }
        }
    }
}
